# # Definition for singly-linked list.
# # class ListNode(object):
# #     def __init__(self, x):
# #         self.val = x
# #         self.next = None
#
# class Solution(object):
#     def sortList(self, head):
#         """
#         :type head: ListNode
#         :rtype: ListNode
#         """
#         if not head or not head.next:
#             return head
#         mid = self.findMid(head)
#         l = self.sortList(head)
#         r = self.sortList(mid)
#         return self.merge(l, r)
#
#     def merge(self, l, r):
#         head = ListNode(0)
#         ini_head = head
#         while l and r:
#             if l.val < r.val
#                 head.next = l
#                 l = l.next
#             else:
#                 head.next = r
#                 r = r.next
#             head = head.next
#         if l:
#             head.next = l
#         if r
#             head.next = r
#         return ini_head.next
#
#
#     def findMid(self, head):
#         slow, fast = head, head
#         while fast.next and fast.next.next:
#             slow = slow.next
#             fast = fast.next.next
#         res = slow.next
#         slow.next = None
#         return res
class Solution():
    def sortList(self, head):
        if not head or not head.next:
            return head
        l, r, m = ListNode(0), ListNode(0), ListNode(0)
        ll, rr, mm = l, r, m
        pivix = head.val
        while head:
            if head.val < pivix:
                ll.next = head
                ll = ll.next
            elif head.val > pivix:
                rr.next = head
                rr = rr.next
            else:
                mm.next = head
                mm = mm.next
            head = head.next
        ll.next = None
        rr.next = None

        l.next = self.sortList(l.next)
        r.next = self.sortList(r.next)
        ll = l
        while ll.next:
            ll = ll.next
        ll.next = m.next
        mm.next = r.next
        return l.next



